2008/01/30

ロカポーター誕生の記録(3)

3.試行錯誤と勉強のやり直し!

その後、どうせ圧縮するなら敢えてロカポを使う必要もないし、いろいろなフォーマットの位置情報コードを作って、それぞれで圧縮効果とか、可逆性が保障されているかを検討しながら試行錯誤することにしました。

同時に、本格的な情報圧縮技術について、昔やった記憶があいまいなので再度勉強開始。ホフマン符号化、LZ法、ランレングス法など。難しいな あ。。。考えた人凄ーい、と思いながら、エクセルベースで簡単なプログラムを組みつつ、いろんな経路情報を実際に符号化して、どれくらい圧縮できるかテス ト。こちらはアルゴリズムが複雑怪奇でもいいから、とにかく圧縮効率だけを追及する「ロカポ圧縮MAX」として別バージョンで出すつもりでした。

経路や領域の情報は、隣り合う点同士は値の変化が少ないので、データ同士の差分を取る方式やMPEG(画像の中の動く部分だけを検出して保存)みたいな方法が向いている。でも一般の情報圧縮は主にFAX画像や音声や映像、テキスト文書をターゲットに開発された歴史もあるので、なんとか経路や領域という地理情報特有の特徴をうまく利用した圧縮アルゴリズムができないか、いろいろ考えました。

たとえば、都道府県とか、マピオンの国獲りみたいな、ある面を複数の領域を分割したデータでは、県境などの境界にあたる部分は二つの領域で共有されている。一辺が接している二つの正方形を思い浮べて頂くとわかりやすいが、この場合接している辺の情報は、二つの正方形領域の情報にそれぞれ含まれている。両方の正方形を、4つの辺の集まりとしてバラすと、共有している辺は順番の正逆はあるかもしれないが、符号以外は同じデータ列なので、これを利用して圧縮できないか、など。
このアイデアはまだLocaPorterでは実現できていないが、領域分割のデータを圧縮するにはとても効果的かなと思っている。(ここで発表してしまったので、特許にはできないですが。笑)

こんな感じで、いろいろ考えたというよりは、エクセルでマクロとVBAでプロトタイプを作っては比較するということを繰り返しました。

4.に続く

0 件のコメント: